题目分析

这个题目是一个数学问题，如果数字很小的话可以迭代求解，但是一旦超过20以上，就变得较为复杂，因为阶乘的数值比指数还要爆炸，在n较大的时候，long类型都无法表示，即使Python语言也会计算的非常慢，小伙伴们能够想到不用计算的好办法吗？

数学

阶乘尾数为0，说明这个数是一个偶数和5相乘的结果，这里也可以看成2和5相乘的结果，因为偶数都可以写成2k。如12!，当乘5的时候，会在尾部增加一个0，是因为有偶数的积累在5之前有2和4，可以积累出3个2相乘，在乘5的时候会消耗一个2，得到一个0，这是这个问题的精髓所在。

因此可以设置一个偶数计数器和一个尾数计数器，当一个数有因子2时，偶数计数器+1，然后继续分解因子，直到无法分解时，继续分解下一个数。当这个数有因子5时，偶数计数器-1，尾数计数器+1，同样继续分解。迭代到n时，如果偶数计数器大于等于0，说明有多余的2，所有的5都匹配成了10，返回尾数计数器的个数。如果偶数计数器小于0，说明5的个数大于2的个数，返回尾数计数器 + 偶数计数器即可。

算法的**时间复杂度为$O(nlog(n))$，空间复杂度为$O(1)$**。

#include<iostream>
#include<algorithm>

using namespace std;

class Solution {
public:
    int trailingZeroes(int n) {
        int res = 0, evenCnt = 0;
        for (int i = 1; i <= n; i++) {
            int tmp = i;
            while (!(tmp & 1)) {
                evenCnt++;
                tmp >>= 1;
            }
            while (!(tmp % 5)) {
                evenCnt--;
                res++;
                tmp /= 5;
            }
        }
        return res + min(evenCnt, 0);
    }
};

优化数学

上面的写法虽然能得到正确结果，但是会TLE，主要原因是样例的数据太大，有1e8量级的数据，只能使用log(n)的算法进行求解。

我们发现了一个规律，偶数出现的次数是一定大于5出现的次数的。因为间隔1个数就会出现一个偶数，间隔4个数才会出现1个5的倍数。因此我们只需要统计5出现的次数，尾数就有多少个0。

如果我们仍然使用上面的方法，一个数一个数进行枚举，这也是没用的，复杂度没有发生变化。我们想n!中有多少个5，以32为例，5，10，15，20，25，30中至少含有一个5，因此有32 / 5 = 6个元素含有一个5，那么这些数除以5以后变为1，2，3，4，5，6，这里面又会有一个5，因此6 / 5 = 1个元素含有5。

小伙伴们是不是已经知道了如何求解。

算法的**时间复杂度为$O(log(n))$，空间复杂度为$O(1)$**。

#include<iostream>
#include<algorithm>

using namespace std;

class Solution {
public:
    int trailingZeroes(int n) {
        int res = 0;
        while (n) {
            n /= 5;
            res += n;
        }
        return res;
    }
};

刷题总结

这种题目基本上已经不会出现在面试中，因为过于简单，也不能排除有些公司特别喜欢考察算法题，先来一些简单题目预热，题目不难，如果之前没有遇到过还是可能做不出来。